本文介绍两种高度相似的数据结构——栈（stack）和队列（queue）。
栈和队列均支持一下两种操作：
此外，为了调试方便，我们还允许显示其中的元素。
要实现栈和队列，一般有两种方式：采用数组或者链表。
在C++中，数组大小是一定的，但是占用空间相对较少，而链表可以动态扩展其长度，但是比较耗空间，实际使用时可以根据需求自己选定。
以下是本人用C++编辑的代码：
基于数组的栈实现：
// Header file: stackBasedOnArray.h
// Implementation of a stack based on an array.
// Edited by Sunshy.
// Home page: http://blog.csdn.net/longyindiyi
// Weibo: @云端暮雪
// 2014.03.19
#ifndef STACKBASEDONARRAY_EDITED_BY_SUN
#define STACKBASEDONARRAY_EDITED_BY_SUN
#define INIT_STACKA_SIZE_EDITED_BY_SUN 100
#include <iostream>
template<class DATATYPE>
class stackBasedOnArray
{
private:
unsigned int numberOfElements; // the size of stack
unsigned int top; // the top index of the stack
bool isSuccessIndex; //
DATATYPE *stack; // elements of the stack
void initStack()
{
stack = new DATATYPE[numberOfElements];
for(unsigned int i = 0; i < numberOfElements; i ++)
{
stack[i] = 0;
}
isSuccessIndex = true;
top = 0;
}
public:
// Constructor function: if user don‘t give any parameter,
// then the size of the stack is initialized to be INIT_STACKA_SIZE_EDITED_BY_SUM,
// which is defined above.
stackBasedOnArray()
{
numberOfElements = INIT_STACKA_SIZE_EDITED_BY_SUN;
initStack();
}
// Constructor function with a initialized parameter
// Input:
// numberOfElementsGivenByUser - initialize the size of the stack.
stackBasedOnArray(unsigned int numberOfElementsGivenByUser)
{
numberOfElements = numberOfElementsGivenByUser;
initStack();
}
// Deconstructor Function
~stackBasedOnArray()
{
delete []stack;
}
// Function - To check if the stack is an empty one.
// Returning a bool value.
bool stackBasedOnArray::isEmpty()
{
if(top == 0)
return true;
else
return false;
}
// Function - To check if the pop or push operation is successfully done.
// Returning a bool value.
// Note: This funciton works only if it is used right after a push or pop operation has been done.
bool stackBasedOnArray::isSuccess()
{
return isSuccessIndex;
}
// Function - To get the size of the stack.
// Returning the size of the stack.
unsigned int stackBasedOnArray::getSize()
{
return numberOfElements;
}
// Function - To get the useful size of the stack.
// Returning the top index of the stack.
unsigned int stackBasedOnArray::getTop()
{
return top;
}
// Funcion - To push a value into the stack.
// Input:
// userValue - the value you want to push to the stack.
// Returning no value.
void stackBasedOnArray::push(DATATYPE userValue)
{
isSuccessIndex = false;
if(top >= numberOfElements)
{
return;
}
stack[top] = userValue;
top ++;
isSuccessIndex = true;
return;
}
// Funcion - To pop a value from the stack.
// Returning the value poped from the stack.
DATATYPE stackBasedOnArray::pop()
{
isSuccessIndex = false;
if(top == 0)
{
return false;
}
top --;
isSuccessIndex = true;
return true;
}
// Function - To print the message of the stack.
void stackBasedOnArray::print()
{
if(isEmpty())
{
return;
}
std::cout<<‘\n‘;
std::cout<<"Stack:"<<‘\n‘;
std::cout <<"Maximum Size: "<<getSize()<<‘\n‘;
std::cout <<"Current Size: "<<getTop()<<‘\n‘;
std::cout <<"Values: "<<‘\n‘;
for(unsigned int i = 0; i < top; i++)
{
cout<<stack[i]<<‘\t‘;
}
std::cout<<‘\n‘;
return;
}
};
#endif基于数组的队列实现：
// Header file: queueBasedOnArray.h
// Implementation of a queue based on an array.
// Edited by Sunshy.
// Home page: http://blog.csdn.net/longyindiyi
// Weibo: @云端暮雪
// 2014.03.19
#ifndef QUEUEBASEDONARRAY_EDITED_BY_SUN
#define QUEUEBASEDONARRAY_EDITED_BY_SUN
#define INIT_QUAEUEA_SIZE_EDITED_BY_SUN 100
#include <iostream>
template<class DATATYPE>
class queueBasedOnArray
{
private:
unsigned int queueSize; // the size of queue
unsigned int head; // the head of the queue
unsigned int tail; // the tail of the queue
bool isSuccessIndex; //
bool isFullIndex;
DATATYPE *queue; // elements of the queue
// Initializing the queue in conduct function.
void initQueue()
{
queue = new DATATYPE[queueSize];
for(unsigned int i = 0; i < queueSize; i++)
{
queue[i] = 0;
}
isSuccessIndex = true;
isFullIndex = false;
head = 0;
tail = 0;
}
public:
// Constructor function: if user don‘t give any parameter,
// then the size of the queue is initialized to be INIT_QUAEUEA_SIZE_EDITED_BY_SUN,
// which is defined above.
queueBasedOnArray()
{
queueSize = INIT_QUAEUEA_SIZE_EDITED_BY_SUN;
initQueue();
}
// Constructor function with a initialized parameter
// Input:
// queueSizeGivenByUser - initialize the size of the queue.
queueBasedOnArray(unsigned int queueSizeGivenByUser)
{
queueSize = queueSizeGivenByUser;
initQueue();
}
// Deconstructor Function
~queueBasedOnArray()
{
delete []queue;
}
// Function - To check if the queue is an empty one.
// Returning a bool value.
bool queueBasedOnArray::isEmpty()
{
if(head == tail && isFullIndex == false)
return true;
else
return false;
}
// Function - To check if the queue is an full one.
// Returning a bool value.
bool queueBasedOnArray::isFull()
{
return isFullIndex;
}
// Function - To check if the enqueue or dequeue operation is successfully done.
// Returning a bool value.
// Note: This funciton works only if it is used right after a enqueue or dequeue operation has been done.
bool queueBasedOnArray::isSuccess()
{
return isSuccessIndex;
}
// Function - To get the size of the queue.
// Returning the size of the queue.
unsigned int queueBasedOnArray::getSize()
{
return queueSize;
}
// Function - To get the useful size of the queue.
// Returning the top index of the queue.
unsigned int queueBasedOnArray::getUsedSize()
{
if(isEmpty())
return 0;
if(tail > head)
return tail - head;
else
return queueSize - (head - tail);
}
// Funcion - To enqueue a value into the queue.
// Input:
// userValue - the value you want to enqueue to the queue.
// Returning no value.
void queueBasedOnArray::enqueue(DATATYPE userValue)
{
if(isFull())
{
isSuccessIndex = false;
return;
}
queue[tail] = userValue;
if(tail == queueSize - 1)
tail = 0;
else
tail ++;
if(tail == head)
isFullIndex = true;
isSuccessIndex = true;
return;
}
// Funcion - To dequeue a value from the queue.
// Returning the value dequeued from the queue.
DATATYPE queueBasedOnArray::dequeue()
{
if(isEmpty())
{
isSuccessIndex = false;
return false;
}
if(head == queueSize - 1)
head = 0;
else
head ++;
isFullIndex = false;
isSuccessIndex = true;
return true;
}
// Function - To print the message of the queue.
void queueBasedOnArray::print()
{
if(isEmpty())
{
std::cout<<‘\n‘;
std::cout<<"Queue:"<<‘\n‘;
std::cout <<"Maximum Size: "<<getSize()<<‘\n‘;
std::cout <<"Current Size: "<<getUsedSize()<<‘\n‘;
std::cout<<‘\n‘;
return;
}
std::cout<<‘\n‘;
std::cout<<"Queue:"<<‘\n‘;
std::cout <<"Maximum Size: "<<getSize()<<‘\n‘;
std::cout <<"Current Size: "<<getUsedSize()<<‘\n‘;
std::cout <<"Values: "<<‘\n‘;
for(unsigned int i = 0; i < getUsedSize(); i++)
{
if((head + i) < queueSize)
cout<<queue[head + i]<<‘\t‘;
else
cout<<queue[i - (queueSize - head)]<<‘\t‘;
}
std::cout<<‘\n‘;
return;
}
};
#endif基于链表的栈实现：
// Header file: stackBasedOnSingleLinkList.h
// Implementation of a stack based on an single link list.
// Edited by Sunshy.
// Home page: http://blog.csdn.net/longyindiyi
// 2014.03.20
// Weibo: @云端暮雪
#ifndef STACKBASEDONSINGLELINKLIST_EDITED_BY_SUN
#define STACKBASEDONSINGLELINKLIST_EDITED_BY_SUN
#define INIT_STACKSLL_SIZE_EDITED_BY_SUN 100
#include <iostream>
template<class DATATYPE>
class stackBasedOnSingleLinkList
{
private:
struct node
{
DATATYPE value;
node *next;
};
unsigned int stackSize; // the size of stack
unsigned int currentSize;
bool isSuccessIndex;
node *head;
public:
// Constructor function: if user don‘t give any parameter,
// then the size of the stack is initialized to be INIT_STACKSLL_SIZE_EDITED_BY_SUN,
// which is defined above.
stackBasedOnSingleLinkList()
{
head = NULL;
stackSize = INIT_STACKSLL_SIZE_EDITED_BY_SUN;
currentSize = 0;
isSuccessIndex = false;
}
// Constructor function with a initialized parameter
// Input:
// stackSizeGivenByUser - initialize the size of the stack.
stackBasedOnSingleLinkList(unsigned int stackSizeGivenByUser)
{
head = NULL;
stackSize = stackSizeGivenByUser;
currentSize = 0;
isSuccessIndex = false;
}
// Deconstructor Function
~stackBasedOnSingleLinkList()
{
while(!isEmpty())
{
pop();
}
}
// Function - To check if the stack is an empty one.
// Returning a bool value.
bool stackBasedOnSingleLinkList::isEmpty()
{
return currentSize == 0;
}
// Function - To check if the pop or push operation is successfully done.
// Returning a bool value.
// Note: This funciton works only if it is used right after a push or pop operation has been done.
bool stackBasedOnSingleLinkList::isSuccess()
{
return isSuccessIndex;
}
// Function - To get the size of the stack.
// Returning the size of the stack.
unsigned int stackBasedOnSingleLinkList::getMaxSize()
{
return stackSize;
}
// Function - To get the useful size of the stack.
// Returning the top index of the stack.
unsigned int stackBasedOnSingleLinkList::getCurrentSize()
{
return currentSize;
}
// Funcion - To push a value into the stack.
// Input:
// userValue - the value you want to push to the stack.
// Returning no value.
void stackBasedOnSingleLinkList::push(DATATYPE userValue)
{
if(getCurrentSize() >= getMaxSize())
{
isSuccessIndex = false;
return;
}
isSuccessIndex = true;
if(head == NULL)
{
head = new node;
head->value = userValue;
head->next = NULL;
currentSize++;
return;
}
node *newNode = new node;
newNode->value = userValue;
newNode->next = head;
head = newNode;
currentSize++;
newNode = NULL;
delete newNode;
return;
/*newNode->next = usernode;*/
}
// Funcion - To pop a value from the stack.
// Returning the value poped from the stack.
DATATYPE stackBasedOnSingleLinkList::pop()
{
if(isEmpty())
{
isSuccessIndex = false;
return NULL;
}
DATATYPE rel = head->value;
node *newNode = new node;
newNode = head->next;
head = newNode;
currentSize--;
isSuccessIndex = true;
newNode = NULL;
delete newNode;
return rel;
}
// Function - To print the message of the stack.
void stackBasedOnSingleLinkList::print()
{
std::cout<<‘\n‘;
std::cout<<"Stack:"<<‘\n‘;
std::cout <<"Maximum Size: "<<getMaxSize()<<‘\n‘;
std::cout <<"Current Size: "<<getCurrentSize()<<‘\n‘;
std::cout <<"Values: "<<‘\n‘;
node *newNode = head;
while(newNode != NULL)
{
std::cout<<newNode->value<<‘\t‘;
newNode = newNode->next;
}
std::cout<<‘\n‘;
newNode = NULL;
delete newNode;
return;
}
};
#endif基于数组的队列实现：
// Header file: stackBasedOnSingleLinkList.h
// Implementation of a stack based on an single link list.
// Edited by Sunshy.
// Home page: http://blog.csdn.net/longyindiyi
// Weibo: @云端暮雪
// 2014.03.20
#ifndef QUEUEBASEDONSINGLELINKLIST_EDITED_BY_SUN
#define QUEUEBASEDONSINGLELINKLIST_EDITED_BY_SUN
#define INIT_QUEUESLL_SIZE_EDITED_BY_SUN 100
#include <iostream>
template<class DATATYPE>
class queueBasedOnSingleLinkList
{
private:
// Linklist node
struct node
{
DATATYPE value;
node *next;
};
unsigned int queueSize; // the maximum size of stack
unsigned int currentSize; // the current size of stack
bool isSuccessIndex;
node *head;
public:
// Constructor function: if user don‘t give any parameter,
// then the size of the queue is initialized to be INIT_QUEUESLL_SIZE_EDITED_BY_SUN,
// which is defined above.
queueBasedOnSingleLinkList()
{
head = NULL;
queueSize = INIT_QUEUESLL_SIZE_EDITED_BY_SUN;
currentSize = 0;
isSuccessIndex = true;
}
// Constructor function with a initialized parameter
// Input:
// queueSizeGivenByUser - initialize the size of the queue.
queueBasedOnSingleLinkList(unsigned int queueSizeGivenByUser)
{
head = NULL;
queueSize = queueSizeGivenByUser;
currentSize = 0;
isSuccessIndex = true;
}
// Deconstructor Function
~queueBasedOnSingleLinkList()
{
while(!isEmpty())
{
dequeue();
}
}
// Function - To check if the queue is an empty one.
// Returning a bool value.
bool queueBasedOnSingleLinkList::isEmpty()
{
return currentSize == 0;
}
// Function - To check if the enqueue or dequeue operation is successfully done.
// Returning a bool value.
// Note: This funciton works only if it is used right after a enqueue or dequeue operation has been done.
bool queueBasedOnSingleLinkList::isSuccess()
{
return isSuccessIndex;
}
// Function - To get the maximum size of the queue.
// Returning the maximum size of the queue.
unsigned int queueBasedOnSingleLinkList::getMaxSize()
{
return queueSize;
}
// Function - To get the useful size of the queue.
// Returning the current size of the queue.
unsigned int queueBasedOnSingleLinkList::getCurrentSize()
{
return currentSize;
}
// Funcion - To enqueue a value into the queue.
// Input:
// userValue - the value you want to enqueue to the queue.
// Returning no value.
void queueBasedOnSingleLinkList::enqueue(DATATYPE userValue)
{
if(getCurrentSize() >= getMaxSize())
{
isSuccessIndex = false;
return;
}
isSuccessIndex = true;
if(head == NULL)
{
head = new node;
head->value = userValue;
head->next = NULL;
currentSize++;
return;
}
node *newNode = new node;
newNode->value = userValue;
newNode->next = NULL;
head->next = newNode;
currentSize++;
newNode = NULL;
delete newNode;
return;
}
// Funcion - To dequeue a value from the queue.
// Returning the value dequeued from the queue.
DATATYPE queueBasedOnSingleLinkList::dequeue()
{
if(isEmpty())
{
isSuccessIndex = false;
return NULL;
}
DATATYPE rel = head->value;
node *newNode = new node;
newNode = head->next;
head = newNode;
currentSize--;
isSuccessIndex = true;
newNode = NULL;
delete newNode;
return rel;
}
// Function - To print the message of the queue.
void queueBasedOnSingleLinkList::print()
{
std::cout<<‘\n‘;
std::cout<<"Queue:"<<‘\n‘;
std::cout <<"Maximum Size: "<<getMaxSize()<<‘\n‘;
std::cout <<"Current Size: "<<getCurrentSize()<<‘\n‘;
std::cout <<"Values: "<<‘\n‘;
node *newNode = head;
while(newNode != NULL)
{
std::cout<<newNode->value<<‘\t‘;
newNode = newNode->next;
}
std::cout<<‘\n‘;
newNode = NULL;
delete newNode;
return;
}
};
#endif以上代码仅供参考，本人测试可以正常工作。
原文：http://blog.csdn.net/yunduanmuxue/article/details/23449647