定义
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。即：
栈：后进先出（LIFO-last in first out）:后进先出。
队列：先进先出（FIFO-first in first out）:先进先出。
栈实现
#stack.h
#ifndef STACK_H
#define STACK_H
#define LENGTH 10
class Stack
{
private:
float *elements;
float *head;
float *tail;
public:
Stack() { elements = new float[LENGTH]; head = elements; tail = nullptr; }
Stack(float arr[],int n)
{
elements = new float[LENGTH];
head = tail = elements;
for (int i = 0; i < n; i++)
*(elements + i) = arr[i];
tail = head + n - 1;
}
bool isempty();
void clear();
float push(float);
float pop();
float top();
void show();
~Stack() { clear(); }
};
#endif // !STACK_H
#stcak.cpp
#include <iostream>
#include "stack.h"
using std::cout;
bool Stack::isempty()
{
return tail == nullptr;
}
void Stack::clear()
{
tail = nullptr;
delete elements;
}
float Stack::push(float a)
{
if (isempty())
{
tail = head;
return *head = a;
}
else
{
tail++;
return *tail = a;
}
}
float Stack::pop()
{
if (!isempty())
if (tail == head)
{
tail = nullptr;
return *head;
}
else
return *tail--;
else
return 0;
}
float Stack::top()
{
return (!isempty()) ? *tail : 0;
}
void Stack::show()
{
for (int i = 0; i <= (tail - head); i++)
cout << *(head + i) << " ";
}
#main.cpp
#include <iostream>
#include "stack.h"
#include <crtdbg.h>
using std::cout;
using std::endl;
int main()
{
float arr[] = { 1,2,3 };
Stack stack1, stack2(arr, 3);
cout << stack1.isempty() << endl;
cout << stack1.push(7) << endl;
cout << stack1.push(8) << endl;
cout << stack1.push(9) << endl;
stack1.show();
cout << endl;
cout << stack1.top() << endl;
cout << stack1.pop() << endl;
cout << stack1.pop() << endl;
stack1.clear();
cout << stack1.isempty() << endl;
cout << stack2.isempty() << endl;
cout << stack2.push(7) << endl;
cout << stack2.push(8) << endl;
cout << stack2.push(9) << endl;
stack2.show();
cout << endl;
cout << stack2.top() << endl;
cout << stack2.pop() << endl;
cout << stack2.pop() << endl;
stack2.clear();
cout << stack2.isempty() << endl;
_CrtDumpMemoryLeaks();
system("pause");
return 0;
}
队列实现
#queue.h
#ifndef QUEUE_H
#define QUEUE_H
#define LENGTH 10
class Queue
{
private:
float *elements;
float *head;
float *tail;
public:
Queue() { elements = new float[LENGTH]; head = elements; tail = nullptr; };
Queue(float arr[], int n)
{
elements = new float[LENGTH];
head = tail = elements;
for (int i = 0; i < n; i++)
*(elements + i) = arr[i];
tail = head + n - 1;
}
bool isempty();
float enqueue(float);
float dequeue();
float bottom();
void show();
void clear();
~Queue() { clear(); }
};
#endif // !QUEUE_H
#include <iostream>
#include "queue.h"
using std::cout;
using std::endl;
bool Queue::isempty()
{
return tail == nullptr;
}
float Queue::enqueue(float num)
{
if (!isempty())
{
*(++tail) = num;
return *tail;
}
else
{
tail = head;
return *tail = num;
}
}
float Queue::dequeue()
{
if (tail != nullptr)
if (head != tail)
{
tail--;
return *(tail + 1);
}
else
{
tail = nullptr;
return *head;
}
else
return 0;
}
float Queue::bottom()
{
return (!isempty()) ? *head : 0;
}
void Queue::show()
{
if (!isempty())
for (int i = 0; i <= tail - head; i++)
cout << *(head + i) << " ";
}
void Queue::clear()
{
tail = nullptr;
delete elements;
}
#main.cpp
#include <iostream>
#include "queue.h"
#include <crtdbg.h>
using std::cout;
using std::endl;
int main()
{
float arr[] = { 1,2,3 };
Queue queue1, queue2(arr, 3);
cout << queue1.isempty() << endl;
cout << queue1.enqueue(7) << endl;
cout << queue1.enqueue(8) << endl;
cout << queue1.enqueue(9) << endl;
queue1.show();
cout << endl;
cout << queue1.bottom() << endl;
cout << queue1.dequeue() << endl;
cout << queue1.dequeue() << endl;
queue1.clear();
cout << queue1.isempty() << endl;
cout << queue2.isempty() << endl;
cout << queue2.enqueue(7) << endl;
cout << queue2.enqueue(8) << endl;
cout << queue2.enqueue(9) << endl;
queue2.show();
cout << endl;
cout << queue2.bottom() << endl;
cout << queue2.dequeue() << endl;
cout << queue2.dequeue() << endl;
queue2.clear();
cout << queue2.isempty() << endl;
_CrtDumpMemoryLeaks();
system("pause");
return 0;
}
参考资料
1. C++数据结构与算法：https://item.jd.com/29739898993.html
