利用 C++ 單向連結清單實作隊列

利用C++ 單向連結清單實作資料結構隊列，其實和上一篇基本内容相同，僅僅是插入的時候在連結清單的尾部插入，取元素都是一樣的，都從頭部取。

#pragma once

#include "stdio.h"
//利用連結清單來實作隊列，先進先出

class queue
{
public:
	queue(void);
	queue(int value);
	~queue(void);
private:
	int m_value;
	queue* m_pnext;
public:
	void push(int value);
	bool pop(int *value);
	bool top(int *value);
	bool empty();
	int size();
	void output();
	void destroy();
};

#include "stdafx.h"
#include "queue.h"


//構造一個空的隊列頭指針
queue::queue(void)
{
	m_value = 0x00;
	m_pnext = NULL;
}

//建構一個隊列結點
queue::queue(int value)
{
	m_value = value;
	m_pnext = NULL;
}

//輸出被删除掉的結點
queue::~queue(void)
{
	printf("destroy node its value=%d\n", m_value);
}

//元素入隊列
void queue::push(int value)
{
	queue *pnode = this;
	while(pnode->m_pnext != NULL)
	{
		pnode = pnode->m_pnext;
	}
	queue *newnode = new queue(value);
	pnode->m_pnext = newnode;
	m_value++;
}


//元素出隊列
bool queue::pop(int *value)
{
	bool result = false;
	if (m_pnext != NULL)
	{
		*value = m_pnext->m_value;
		m_pnext = m_pnext->m_pnext;
		result = true;
		m_value--;
	}
	return result;
}

//得到隊列頂部的元素
bool queue::top(int *value)
{
	bool result = false;
	if (m_pnext != NULL)
	{
		*value = m_pnext->m_value;
		result = true;
	}
	return result;
}

//判斷隊列是否為空
bool queue::empty()
{
	bool result = false;
	if (m_pnext == NULL)
	{
		result = true;
	}
	return result;
}

//得到隊列大小
int queue::size()
{
	return m_value;
}


//輸出隊列中的元素
void queue::output()
{
	queue* pnode = this;
	while(pnode->m_pnext != NULL)
	{
		printf("index=%d\n", pnode->m_pnext->m_value);
		pnode = pnode->m_pnext;

	}
}

//銷毀隊列
void queue::destroy()
{
	while(m_pnext != NULL) 
	{
		queue* pnode = m_pnext;
		m_pnext = m_pnext->m_pnext;
		delete pnode;
	}
}

      

主程式測試

// myqueue.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "queue.h"

int _tmain(int argc, _TCHAR* argv[])
{
	queue myqueue;
	for(int i=0; i<10; i++)
	{
		myqueue.push(i * 10);
	}

	myqueue.output();
	printf("queue size=%d\n", myqueue.size());

	if (myqueue.empty())
	{
		printf("queue is empty\n");
	}
	else 
	{
		printf("queue is not empty\n");
	}

	myqueue.destroy();

	int value = 0;
	for(int i=0; i<10; i++)
	{
		if (myqueue.pop(&value))
		{
			printf("pop value=%d successfully\n", value);
		}
		else
		{
			printf("pop unsuccessfully\n");
		}
	}

	printf("queue size=%d\n", myqueue.size());

	if (myqueue.empty())
	{
		printf("queue is empty\n");
	}
	else 
	{
		printf("queue is not empty\n");
	}

	getchar();
	return 0;
}