栈与队列
undefined
栈
栈简介
栈先进者后出，栈是一种操作受限的线性表，只允许一段插入与删除数据。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，就可以选择栈这种数据结构。 用数组实现的栈称为顺序栈，用链表实现的栈称为链表栈 不管是顺序栈还是链式栈，存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。并且入栈还是出栈只会涉及个别数据操作，空间复杂度也为O(1)
栈代码实现
/**
* 基于链表实现的栈
*/
public class StackBaseLinkList {
Node top = null;
public void push(int value){
Node nextNode = new Node(value,null);
//判断栈是否为空
if(top==null){
top = nextNode;
}else {
//nextNode的后继指针next 指向top栈，实现入栈
nextNode.next = top;
top = nextNode;
}
}
//栈为空，返回-1
public int pop(){
if(top==null) return -1;
//一层一层取出入栈的值实现出栈
int value = top.data;
top = top.next;
return value;
}
//打印栈数据
private void printAll(){
Node pNode = top;
while(pNode!=null){
System.out.print(pNode.getData()+"");
pNode = pNode.next;
}
System.out.println(" ");
}
}队列
队列简介
先进先出，入队，放一个数据在尾部，出队，从头部取出数据，队列也是一种操作受限的线性表数据结构。用数组实现的队列叫顺序队列，用链表实现的队列叫链表队列 队列需要两个指针，一个head指针指向对头，一个tail指针指向队尾。
队列代码实现
/**
* 基于链表实现的队列
*/
public class QueueBaseLinkList {
private Node head = null;
private Node tail = null;
//入队
public void equeue(String value){
if(tail==null){
Node newNode = new Node(value, null);
head = newNode;
tail = newNode;
}else {
tail.next = new Node(value, null);
tail = tail.next;
}
}
//出队
public String dequeue(){
if(head==null) return null;
String value = head.data;
head = head.next;
if(head==null){
tail=null;
}
return value;
}
private static class Node{
private String data;
private Node next;
public Node(String data,Node next) {
// TODO Auto-generated constructor stub
this.data = data;
this.next = next;
}
public String getData() {
return data;
}
}
}循环队列
循环队列是队列头部与尾部相连，也就是头指针与尾部指针链接在一起。
/**
* 基于数组实现的循环队列
*
*/
public class CircleQueue {
private String[] items;
private int n=0;
private int head = 0;
private int tail = 0;
public CircleQueue(int capacity) {
// TODO Auto-generated constructor stub
items = new String[capacity];
n = capacity;
}
private boolean equeue(String item){
//队列满
if((tail+1)%n==head) return false;
items[tail] = item;
tail = (tail+1)%n;
return true;
}
private String dequeue(){
//队列为空
if(head == tail) return null;
String value = items[head];
head = (head+1)%n;
return value;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019年8月4日 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录