1. 用棧實現(xiàn)隊列（OJ鏈接）

題目描述：請你僅使用兩個棧實現(xiàn)先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）

void push(int x) 將元素 x 推到隊列的末尾
int pop() 從隊列的開頭移除并返回元素
int peek() 返回隊列開頭的元素
boolean empty() 如果隊列為空，返回 true ；否則，返回 false

假設入隊的順序是1，2，3，4，5，那么出隊的順序也需要是1，2，3，4，5
棧的性質是先進后出，但是我們有兩個棧，如果把數(shù)據(jù)pop到另一個棧中，再出數(shù)據(jù)，那么會怎么樣呢？

看下圖。

此時我們從stack2中出數(shù)據(jù)會發(fā)現(xiàn)，出隊的順序變成了1，2，3，4，5
此時需要進數(shù)據(jù)的話，就需要進入到stack1，當stack2為空時，若需要pop數(shù)據(jù)，則將stack1的數(shù)據(jù)倒到stack2中再進行pop。

那么push和pop操作就可以理解為：有兩個棧，stack1和stack2，push數(shù)據(jù)時永遠push到stack1中，pop數(shù)據(jù)從stack2中pop，如果stack2為空，那么將stack1中的數(shù)據(jù)全部倒到stack2中，再進行pop。

peek操作為獲取隊頭元素，由于經(jīng)過一輪的倒入，再stack2中的棧頂數(shù)據(jù)就是隊頭了，直接返回該數(shù)據(jù)即可，如果stack2為空，則需要先從stack1中入數(shù)據(jù)到stack2中。

判空操作：兩個棧都為空，那么隊列就為空。

用棧實現(xiàn)隊列，我們需要一個棧的數(shù)據(jù)結構，之前已經(jīng)寫過了，這里直接拷貝過來用即可。
完整代碼如下

typedef int STDataType;

typedef struct StackNode
{
	int capacity;      //最大容量
	int top;           //棧頂數(shù)據(jù)的下一個位置
    STDataType* arr;   //數(shù)組
}STNode;

//初始化順序棧
void StackInit(STNode* ps)
{
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//銷毀棧
void StackDestroy(STNode* ps)
{
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}
//入棧
void StackPush(STNode* ps, STDataType x)
{
	//沒有空間或者空間滿了，先擴容
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->arr,sizeof(STNode) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc()");
			return;
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	//插入數(shù)據(jù)
	ps->arr[ps->top++] = x;

}
//出棧
void StackPop(STNode* ps)
{
	ps->top--;
}
//判斷棧空
bool StackEmpty(STNode* ps)
{
	return ps->top == 0;
}
//獲得棧頂元素
int FindTop(STNode* ps)
{
	return ps->arr[ps->top - 1];
}

typedef struct 
{
    STNode stack1;//push數(shù)據(jù)的棧
    STNode stack2;//pop數(shù)據(jù)的棧
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->stack1);
    StackInit(&obj->stack2);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) 
{
    StackPush(&obj->stack1,x);
}

int myQueuePop(MyQueue* obj) 
{
    //棧一不是空，棧二是空
    if(!StackEmpty(&obj->stack1)&&StackEmpty(&obj->stack2))
    {
        //將數(shù)據(jù)移到棧二
        while(!StackEmpty(&obj->stack1))
        {
            StackPush(&obj->stack2,FindTop(&obj->stack1));
            StackPop(&obj->stack1);
        }
        int ret=FindTop(&obj->stack2);
        StackPop(&obj->stack2);
        return ret;
    }
    //棧二有數(shù)據(jù)，直接pop
    else
    {
        int ret=FindTop(&obj->stack2);
        StackPop(&obj->stack2);
        return ret;
    }
}

int myQueuePeek(MyQueue* obj) 
{
    //棧二沒有數(shù)據(jù)
    if(StackEmpty(&obj->stack2))
    {
        //將棧一的數(shù)據(jù)移到棧二
        while(!StackEmpty(&obj->stack1))
        {
            StackPush(&obj->stack2,FindTop(&obj->stack1));
            StackPop(&obj->stack1);
        }
    }
    //返回棧頂數(shù)據(jù)
    return FindTop(&obj->stack2);
}

bool myQueueEmpty(MyQueue* obj) 
{
    return StackEmpty(&obj->stack1)&&StackEmpty(&obj->stack2);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->stack1);
    StackDestroy(&obj->stack2);
    free(obj);
}

代碼雖然看著很長，但是其中三分之二都是之前寫過的，這里只是拿來運用而已。下一題也是如此。

2. 用隊列實現(xiàn)棧（OJ鏈接）

題目描述：請你僅使用兩個隊列實現(xiàn)一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。

void push(int x) 將元素 x 壓入棧頂。
int pop() 移除并返回棧頂元素。
int top() 返回棧頂元素。
boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。

假設入隊數(shù)據(jù)1，2，3，4，5由于需要實現(xiàn)棧，那么出數(shù)據(jù)的順序需要是5，4，3，2，1，效仿上一題，將數(shù)據(jù)倒入到另一個隊列后，發(fā)現(xiàn)再出數(shù)據(jù)還是1，2，3，4，5，因此這個方法不適用了。

需要出的數(shù)據(jù)是5，所以可以考慮把1，2，3，4倒入到另一個隊列，再把5出出去。把1，2，3倒回來，把4再出出去，循環(huán)就可以實現(xiàn)出數(shù)據(jù)的順序為5，4，3，2，1了

過程如圖所示

最終的數(shù)據(jù)序列就是5，4，3，2，1

push數(shù)據(jù)時，需要往非空的隊列內push，需要后進先出。

pop數(shù)據(jù)時需要將非空隊列的前n-1個數(shù)據(jù)入到空隊列里（假設非空隊列有n個數(shù)據(jù)），再pop最后一個數(shù)據(jù)。

top：棧頂數(shù)據(jù)就是非空隊列的隊尾

empty：兩個隊列都為空，則棧為空

完整代碼如下

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);

void QueuePush(Queue* pq,QDataType x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);

QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

bool QueueEmpty(Queue* pq);

//初始化隊列
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}
//銷毀隊列
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
//隊尾入隊
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	//創(chuàng)建新節(jié)點
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		return;
	}
	newNode->val = x;
	newNode->next = NULL;
	//隊列為空
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newNode;
	}
	//隊列不為空
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}

	pq->size++;
}
//隊頭出隊
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));   //隊列不能為空
	//只有一個結點
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	
	else
	{
		QNode* cur = pq->head->next;  //保留第二個結點
		free(pq->head);
		pq->head = cur;
	}

	pq->size--;
}
//隊列大小
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
//隊頭元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->val;
}
//隊尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->val;
}
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

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) 
{
    //將數(shù)據(jù)插入非空的隊列
    if(QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q2,x);
    }
    else
    {
        QueuePush(&obj->q1,x);
    }
}

int myStackPop(MyStack* obj) 
{
    //找到空的隊列
    Queue* Empty=&obj->q1;
    Queue* NotEmpty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        Empty=&obj->q2;
        NotEmpty=&obj->q1;
    }
    //將非空隊列前n-1個數(shù)據(jù)導入到空隊列
    while(QueueSize(NotEmpty)>1)
    {
        QueuePush(Empty,QueueFront(NotEmpty));
        QueuePop(NotEmpty);
    }
    //pop掉最后一個
    int popData=QueueFront(NotEmpty);
    QueuePop(NotEmpty);
    return popData;

}

int myStackTop(MyStack* obj) 
{
    //棧頂數(shù)據(jù)就是非空隊列的最后一個數(shù)據(jù)
    if(QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q2);
    }
    else
    {
        return QueueBack(&obj->q1);
    }
}

bool myStackEmpty(MyStack* obj) 
{
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) 
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

同樣，三分之二的代碼是之前寫過的，這里只需要拷貝過來使用即可。
運行結果如下圖

3. 設計循環(huán)隊列（OJ鏈接）

題目描述：循環(huán)隊列是一種線性數(shù)據(jù)結構，其操作表現(xiàn)基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環(huán)。

循環(huán)隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環(huán)隊列，我們能使用這些空間去存儲新的值。

你的實現(xiàn)應該支持如下操作：

MyCircularQueue(k): 構造器，設置隊列長度為 k 。
Front: 從隊首獲取元素。如果隊列為空，返回 -1 。
Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。
enQueue(value): 向循環(huán)隊列插入一個元素。如果成功插入則返回真。
deQueue(): 從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。
isEmpty(): 檢查循環(huán)隊列是否為空。
isFull(): 檢查循環(huán)隊列是否已滿。

假設k等于5，即隊列的長度等于5，最多存五個數(shù)據(jù)。
這里采用數(shù)組來實現(xiàn)循環(huán)隊列。

定義的結構體類型如下

typedef struct {
    int* a;      //數(shù)組
    int front;   //指向隊頭
    int tail;    //指向隊尾下一個位置
    int k;       //隊列元素個數(shù)
} MyCircularQueue;

開辟k個空間會有上述的歧義，所以選擇多開一個空間，即開辟k+1個空間，那么隊列為空時是front=tail

將上面兩種情況綜合，隊列為滿時判斷條件是 ( tail + 1 ) % ( k + 1 ) = front;

出隊和入隊也需要注意下標的回繞，也就是求余操作，也可以使用判斷語句。

完整代碼如下

typedef struct {
    int* a;      //數(shù)組
    int front;   //指向隊頭
    int tail;    //指向隊尾下一個位置
    int k;       //隊列元素個數(shù)
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->tail=0;
    obj->k=k;
    return obj;
}

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->tail;
}
//判滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1)==obj->front;
}
//入隊
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //隊列滿了
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //入隊
    obj->a[obj->tail++]=value;
    //下標回繞
    if(obj->tail==obj->k+1)
    {
        obj->tail=0;
    }
    return true;
}
//出隊
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //隊列為空
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //出隊
    obj->front++;
    //下標回繞
    if(obj->front==obj->k+1)
    {
        obj->front=0;
    }
    return true;
}
//隊頭元素
int myCircularQueueFront(MyCircularQueue* obj) {
    //空隊列返回-1
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[obj->front];
}
//隊尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    //空隊列返回-1
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //返回最后一個值
    if(obj->tail==0)
    {
        return obj->a[obj->k];
    }
    return obj->a[obj->tail-1];
}
//釋放空間
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

關于棧和隊列的題目，就寫到這里了。文章來源地址http://www.zghlxwxcb.cn/news/detail-848031.html

到了這里，關于數(shù)據(jù)結構OJ題——棧和隊列的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！