栈的特性是先进后出(FILO)。
压栈：栈的插入 *** 作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除 *** 作叫做出栈。出数据也在栈顶。
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的
代价比较小。
以下是c语言代码实现：
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_top = 0;
ps->_capacity = 0;
}
void StackPush(Stack* ps, STDataType data)
{
if (ps->_top == ps->_capacity)
{
int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
int* tmp = (int*)realloc(ps->_a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
ps->_a = tmp;
ps->_capacity = newcapacity;
}
ps->_a[ps->_top] = data;
ps->_top++;
}
void StackPop(Stack* ps)
{
assert(ps);
ps->_top--;
}
void Stackprint(Stack* ps)
{
assert(ps);
for (int i = 0; i < ps->_top; i++)
{
printf("%d ", ps->_a[i]);
}
}
STDataType StackTop(Stack* ps)
{
assert(ps);
return ps->_a[ps->_top - 1];
}
int StackSize(Stack* ps)
{
return ps->_top;
}
int StackEmpty(Stack* ps)
{
return ps->_top == 0;
}
void StackDestroy(Stack* ps)
{
free(ps->_a);
ps->_top = 0;
ps->_capacity = 0;
}
队列的特性是先进先出(FIFO)。
进行插入 *** 作的一端称为队尾，进行删除 *** 作的一端称为队头。
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数
组头上出数据，效率会比较低。
以下是c语言代码实现：
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* _next;// 指向下一个节点
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
}
QNode* buynode(int x)
{
QNode* node = (QNode*)malloc(sizeof(QNode));
if (node == NULL)
{
printf("malloc fail");
exit(-1);
}
node->_data = x;
node->_next = NULL;
return node;
}
void QueuePush(Queue* q, QDataType data)
{
assert(q);
if (q->_front == NULL)
{
q->_front= q->_rear=buynode(data);
}
else
{
q->_rear->_next = buynode(data);
q->_rear=q->_rear->_next;
}
}
void Queueprint(Queue* q)
{
assert(q);
QNode* cur = q->_front;
while (cur != NULL)
{
printf("%d ", cur->_data);
cur = cur->_next;
}
printf("\n");
}
void QueuePop(Queue* q)
{
assert(q);
if (q->_front == q->_rear)
{
free(q->_front);
q->_front = q->_rear = NULL;
}
else
{
QNode* tmp = q->_front->_next;
free(q->_front);
q->_front = tmp;
}
}
QDataType QueueFront(Queue* q)
{
assert(q);
return q->_front->_data;
}
QDataType QueueBack(Queue* q)
{
assert(q);
return q->_rear->_data;
}
int QueueSize(Queue* q)
{
assert(q);
int cnt = 0;
QNode* cur = q->_front;
while (cur != NULL)
{
cnt++;
cur = cur->_next;
}
return cnt;
}
int QueueEmpty(Queue* q)
{
assert(q);
return q->_front == NULL;
}
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->_front;
while (cur != NULL)
{
QNode* next = cur->_next;
free(cur);
cur = next;
}
q->_front = q->_rear = NULL;
}
总体的思想就是把数据push到非空队列中，当pop时把非空队列的前n-1个数据全部转移到空队列中，把非空队列最后一个数据pop掉，就能完成栈的FILO。
// 首先我们要有一个栈，可以自己写或者使用C++的stl中提供的
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate()
{
MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
QueueInit(&(obj->q1));
QueueInit(&(obj->q2));
return obj;
}
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj)
{
Queue*empty=&obj->q1;
Queue*noempty=&obj->q2;
if(!QueueEmpty(&obj->q1))
{
empty=&obj->q2;
noempty=&obj->q1;
}
while(QueueSize(noempty)>1)
{
QueuePush(empty,QueueFront(noempty));
QueuePop(noempty);
}
int top=QueueFront(noempty);
QueuePop(noempty);
return top;
}
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1))
{return QueueBack(&obj->q1);}
else
{return QueueBack(&obj->q2);}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
总体思想就是定义两个队列，一个负责push，另一个负责pop，当我们要入数据时全部入在push队列中，当我们要出数据的时候先检查pop队列有没有数据，如果pop队列中有数据，就pop掉pop队列的元素，如果pop队列没有数据，就先把push队列中的数据转移到pop队列中，再pop掉pop队列的元素。
// 首先我们要有一个队列，可以自己写或者使用C++的stl中提供的
typedef struct
{
Stack pushst;
Stack popst;
} MyQueue;
MyQueue* myQueueCreate()
{
MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->pushst);
StackInit(&obj->popst);
return obj;
}
void myQueuePush(MyQueue* obj, int x)
{
StackPush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj)
{
if(StackEmpty(&obj->popst))
{
while(!StackEmpty(&obj->pushst))
{
StackPush(&obj->popst,StackTop(&obj->pushst));
StackPop(&obj->pushst);
}
}
int top=StackTop(&obj->popst);
StackPop(&obj->popst);
return top;
}
int myQueuePeek(MyQueue* obj)
{
if(StackEmpty(&obj->popst))
{
while(!StackEmpty(&obj->pushst))
{
StackPush(&obj->popst,StackTop(&obj->pushst));
StackPop(&obj->pushst);
}
}
int top=StackTop(&obj->popst);
return top;
}
bool myQueueEmpty(MyQueue* obj)
{
return StackEmpty(&obj->pushst)&&StackEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj)
{
StackDestroy(&obj->pushst);
StackDestroy(&obj->popst);
free(obj);
obj=NULL;
}
可以充分利用队列的空间，用数组实现可以更方便地找到最后一个元素，空间可以重复利用。
typedef struct {
int*a;
int k;
int head;
int tail;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue*cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
cq->a=(int*)malloc(sizeof(int)*(k+1));
cq->k=k;
cq->head=cq->tail=0;
return cq;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->head==obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
int next=obj->tail+1;
if(next==obj->k+1)
{
next=0;
}
return next==obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->tail]=value;
obj->tail++;
if(obj->tail==obj->k+1)
{
obj->tail=0;
}
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->head++;
if(obj->head==obj->k+1)
{
obj->head=0;
}
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->head];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
int tail=obj->tail;
tail--;
if(tail==-1)
{
return obj->a[obj->k];
}
return obj->a[obj->tail-1];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）